package com.example.leetcode.trainingcamp.week4.Sunday;

import java.util.*;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]
 * 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 *
 * <p>
 *
 * <p>示例 1：
 *
 * <p>输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠,
 * 将它们合并为 [1,6]. 示例 2：
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-intervals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test56 {

    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        if (len == 1){
            return intervals;
        }
        List<int[]> list = new ArrayList<>();
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x[0]));
        queue.addAll(Arrays.asList(intervals));
        list.add(queue.poll());
        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            int pollMin = poll[0];
            int[] ints = list.get(list.size() - 1);
            int max = ints[1];
            if (max < pollMin){
                list.add(poll);
            }else if (max == pollMin){
                // 说明相等
                ints[1] = poll[1];
                list.remove(list.size()-1);
                list.add(ints);
            }else {
                int pollMax = poll[1];
                if (pollMax > max){
                    ints[1] = poll[1];
                    list.remove(list.size()-1);
                    list.add(ints);
                }
            }
        }
        int[][]result = new int[list.size()][2];
        for (int i = 0;i<list.size();i++){
            result[i] = list.get(i);
        }
        return result;
    }
}


class Demo56{
  public static void main(String[] args) {
    Test56 t = new Test56();
    int[][] intervals = {{1,4},{4,5}};
    int[][] merge = t.merge(intervals);
    for (int[] ints:merge){
      System.out.println(ints[0]+","+ints[1]);
    }
  }
}